﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Collections;
using MPI;

namespace Dwarf.Managed
{
    /// <summary>
    /// Solve the Unstructured Grid problem with MPI parallelization  
    /// </summary>
    /// <remarks> 
    /// For the demonstration purposes of the project, we have chosen two-dimensional iterative triangle grid. 
    /// Function used on each vertex of the grid is arithmetic mean of the neighbors’ vertices. 
    /// The test of convergence performed is the comparison of difference of the same vertices on latest iterations to epsilon.
    /// </remarks>
    class Solver
    {
        /// <summary>
        /// Power of graph.
        /// </summary>
        public int numVertex;
        /// <summary>
        /// Number of triangles in grid.
        /// </summary>
        public int numTriangles;

        /// <summary>
        /// Epsilon.
        /// </summary>
        public double epsilon;

        /// <summary>
        /// Values of verteces.
        /// </summary>
        public double[] vertexValues;
        /// <summary>
        /// Result vertices.
        /// </summary>
        public double[] resultValue;

        /// <summary>
        /// Array for neighbors of each vertex.
        /// </summary>
        public int[][] neighborhood;
        /// <summary>
        /// Verteces of triangles.
        /// </summary>
        public int[][] triangles;

        ///<summary>
        ///local vertices
        ///</summary>
        public int[] localVertices;
        /// <summary>
        /// map numbers - neighbors[].
        /// </summary>
        public Dictionary<int,int[]> localNeighborhood;
        /// <summary>
        /// map numbers - value.
        /// </summary>
        public Dictionary<int,double> localValues;
        /// <summary>
        /// map proc - shadows needed from proc.
        /// </summary>
        public int [][] localShadows;

        /// <summary>
        /// Array of vertex values indexed by localized vertex numbers
        /// </summary>
        private double[] localizedValues;
        /// <summary>
        /// Array of neghborhood arrays indexed by localized vertex numbers
        /// </summary>
        private int[][] localizedNeighbors;
        /// <summary>
        /// Maps localized vertex numbers to original numbers
        /// </summary>
        private int[] localMap;
        /// <summary>
        /// Maps original vertex numbers to localized numbers
        /// </summary>
        private Dictionary<int, int> globalMap;


        /// <summary>
        /// Empty constructor.
        /// </summary>
        public Solver()
        {}

        /// <summary>
        /// Arithmetic mean of the neighbors’ vertices.
        /// </summary>
        private double compute(int[] neighbors, double[] values)
        {
            double output = 0.0;
            foreach (int v in neighbors)
            {
                output += values[v];
            }
            return output / neighbors.Length;
       }

        /// <summary>
        /// MPI based method.
        /// </summary>
        public void Solve()
        {
            //uncomment to see how strongly interconnected the grid is
            //or conversely how poor the graph division is
            //Console.WriteLine("{0} Solve entered with {1} vertices",
            //    Communicator.world.Rank, localVertices.Length);
            //for (var i = 0; i < localShadows.Length; i++)
            //{
            //    Console.WriteLine("{0} Shadows {1} from {2}",
            //        Communicator.world.Rank, localShadows[i].Length, i);
            //}

            bool converged = false;             //Flag of convergance
            var valuesTemp = new double[localizedValues.Length];  //storage for computed values during iteration
            var iterations = 0;

            while (!converged)                  //Loop while the test of convergence for each vertex is not passed
            {
                converged = true;
                iterations++;

                ExchangeShadows();

                //Loop for all local vertices 
                for (var v=0; v<localVertices.Length;v++)
                {
                    var computed = valuesTemp[v] = 
                        compute(localizedNeighbors[v], localizedValues);

                    //Check test of convergence for current vertex.
                    if (converged && (Math.Abs(computed - localizedValues[v]) >= epsilon)) converged = false;
                }

                //setup for next iteration
                var swap = localizedValues;
                localizedValues = valuesTemp;
                valuesTemp = swap;

                //Distribute convergence
                converged = Communicator.world.Allreduce(converged, (x, y) => x && y);
            }

            //Console.WriteLine("{0} iteration {1}",
            //    Communicator.world.Rank, iterations);            
        }


        /// <summary>
        /// Turn all data into local linear representations by renaming the vertices into a local namespace
        /// </summary>
        public void localize()
        {
            //build local to global and local to global maps
            var numShadows = localShadows.Select((s) => s.Length).Sum();
            localMap = new int[localVertices.Length + numShadows];
            globalMap = new Dictionary<int, int>(localMap.Length);

            //fill with local vertices and shadows
            var index = 0;
            for (var i = 0; i < localVertices.Length; i++)
            {
                var v = localVertices[i];
                localMap[index] = v;
                globalMap[v] = index;
                index++;
            }
            for (var proc = 0; proc < localShadows.Length; proc++)
            {
                for (var i = 0; i < localShadows[proc].Length; i++)
                {
                    var v = localShadows[proc][i];
                    localMap[index] = v;
                    globalMap[v] = index;
                    index++;
                }
            }

            //build localized values and fill it
            localizedValues = new double[localMap.Length];
            foreach (var kvpair in localValues)
            {
                localizedValues[globalMap[kvpair.Key]] = kvpair.Value;
            }
            localValues = null;


            //build localized neighbors and fill it
            localizedNeighbors = new int[localVertices.Length][];
            foreach (var kvpair in localNeighborhood)
            {
                var neighbors = kvpair.Value.Select((v) => globalMap[v]).ToArray();
                localizedNeighbors[globalMap[kvpair.Key]] = neighbors;
            }
            localNeighborhood = null;
        }
        /// <summary>
        /// Collect pieces from each process and aggregate back into original vertices array
        /// </summary>
        public void CollectResults()
        {
            //Collect the resulting vertex’s values on root process
            if (Communicator.world.Rank == Settings.ROOT_PROCESS)
            {
                //root values
                foreach (var v in localVertices)
                {
                    vertexValues[v] = localizedValues[globalMap[v]];
                }

                //other procs values
                for (var proc = 1; proc < Communicator.world.Size; proc++)
                {
                    var procVertices = Program.ReceiveArray<int>(proc);
                    var procValues = Program.ReceiveArray<double>(proc);
                    for (var i = 0; i < procVertices.Length; i++)
                    {
                        vertexValues[procVertices[i]] = procValues[i];
                    }
                }
            }
            else
            {
                //send vertices and values to root
                Program.SendArray<int>(localVertices, Settings.ROOT_PROCESS);
                var myValues = new double[localVertices.Length];
                for (var i = 0; i < myValues.Length; i++)
                {
                    myValues[i] = localizedValues[globalMap[localVertices[i]]];
                }
                Program.SendArray<double>(myValues, Settings.ROOT_PROCESS);
            }
            resultValue = vertexValues;
        }

        /// <summary>
        /// Request and supply shadows to all
        /// </summary>
        private void ExchangeShadows()
        {
            //Exchange shadow values -- Loop for all processes
            for (var proc = 0; proc < Communicator.world.Size; proc++)
            {
                if (proc == Communicator.world.Rank)
                {

                    //Request shadow values from other procs
                    for (var other = 0; other < Communicator.world.Size; other++)
                    {
                        if (other == proc) continue;

                        var needed = localShadows[other];
                        Program.SendArray(needed, other);
                        var shadows = Program.ReceiveArray<double>(other);

                        //update (insert into) localizedValues
                        for (var i = 0; i < needed.Length; i++)
                        {
                            localizedValues[globalMap[needed[i]]] = shadows[i];
                        }
                    }
                }
                else
                {
                    //get request for shadows                         
                    MPI.CompletedStatus status;
                    var requested = Program.ReceiveArray<int>(Communicator.anySource, out status);

                    //collect and send them
                    var shadows = new double[requested.Length];
                    for (var i = 0; i < requested.Length; i++)
                    {
                        shadows[i] = localizedValues[globalMap[requested[i]]];
                    }
                    Program.SendArray(shadows, status.Source);
                }
            }
        }

    }
}
